/********************************************************************
	created:	2011/03/02
	created:	2:3:2011   22:12
	filename: 	c:\Users\lian\Documents\Visual Studio 2008\Projects\RASEncryptor\src\LargeIntegerMeta.inl
	file path:	c:\Users\lian\Documents\Visual Studio 2008\Projects\RASEncryptor\src
	file base:	LargeIntegerMeta
	file ext:	inl
	author:		Jincheng Li
	
	purpose:	
*********************************************************************/

#include <stdlib.h>
#include <algorithm>
#include <bitset>
#include <fstream>

#include "TypeDefine.h"

template<typename ELEMT_TYP, int N>
class LargeIntegerMeta {
	template<typename ELEMT_TYP, int N>
	friend class LargeIntegerMeta;

	template<typename T, int N>
	friend std::ostream& operator<<(std::ostream &pStream, const LargeIntegerMeta<T,N>& pData);
public:
	
	static const int ELEMT_SIZE = N;
	static const int ELEMT_BITS = sizeof(ELEMT_TYP) * 8;
	static const int TOTAL_BITS = N * ELEMT_BITS;

	//************************************
	// Default constructor clears the memory.
	//************************************
	LargeIntegerMeta(){
		clearMem();
	}

	//************************************
	// Copy from raw memory.
	// From low bit to high bit.
	// ?Move to private?
	//************************************
	LargeIntegerMeta(const ELEMT_TYP *ppStart){
		memcpy( m_data, ppStart, ELEMT_SIZE * sizeof(ELEMT_TYP) );
	}

	//************************************
	// Temp method. To delete.
	//************************************
	operator UINT32(){
		UINT32 *t = (UINT32*)m_data;
		return *t;
	}

	//************************************
	// Construct from another object with the same element type possibly in different size
	//************************************
	template<int M>
	explicit LargeIntegerMeta(const LargeIntegerMeta<ELEMT_TYP,M>& rhs, const int pElmRightOffset=0){
		assign_right_align<M>(rhs,pElmRightOffset);
	}

	//************************************
	// Operator = only performs on two objects with exactly the same type
	//************************************
	LargeIntegerMeta& operator=(const LargeIntegerMeta& rhs){
		assign_right_align<ELEMT_SIZE>(rhs);
		return *this;
	}

	//************************************
	// Karatsuba algorithm used.
	// Ugly implementation
	//************************************
	LargeIntegerMeta<ELEMT_TYP, 2 * N> operator * (const LargeIntegerMeta& rhs) const
	{
		const int length_n = ELEMT_SIZE>>1;
		const int length_m = ELEMT_SIZE - length_n;//may be longer than n.

		if (1==length_n)
		{
			return mul_4_times(rhs);
		}
		
		LargeIntegerMeta<ELEMT_TYP, length_m> a1(m_data+length_n), b1(rhs.m_data+length_n);
		LargeIntegerMeta<ELEMT_TYP, length_m> a2(m_data), b2(rhs.m_data);

		LargeIntegerMeta<ELEMT_TYP, 2 * length_m> r1 = a1 * b1;
		LargeIntegerMeta<ELEMT_TYP, 2 * length_m> r2 = a2 * b2;

		LargeIntegerMeta<ELEMT_TYP, length_m + 1> a1_l(a1), a2_l(a2), b1_l(b1), b2_l(b2);
		LargeIntegerMeta<ELEMT_TYP, 2 * length_m + 2> r_l_1( (a1_l+a2_l)*(b1_l+b2_l) );
		LargeIntegerMeta<ELEMT_TYP, 2 * length_m + 1> t_r_1(r1), t_r_2(r2); 
		LargeIntegerMeta<ELEMT_TYP, 2 * length_m + 2> r_l_2( t_r_1+t_r_2 );

		LargeIntegerMeta<ELEMT_TYP, 2 * N> retVal(r2);								// copy lower bits
		retVal.merge_right_align( r1, -2 * length_n );								// copy higher bits
		
		//Less optimal...
		LargeIntegerMeta<ELEMT_TYP, 2 * N> sum_l( r_l_1 - r_l_2, -length_n );		// sum of middle bits
		retVal = retVal + sum_l;													// final add.

		return retVal;
	}

	LargeIntegerMeta<ELEMT_TYP, 2 * N> mul_4_times(const LargeIntegerMeta& rhs) const
	{
		const int length_n = ELEMT_SIZE>>1;
		const int length_m = ELEMT_SIZE - length_n;//may be longer than n.

		LargeIntegerMeta<ELEMT_TYP, length_m> a1(m_data+length_n), b1(rhs.m_data+length_n);
		LargeIntegerMeta<ELEMT_TYP, length_n> a2(m_data), b2(rhs.m_data);

		LargeIntegerMeta<ELEMT_TYP, 2 * length_m> r1 = a1 * b1;
		LargeIntegerMeta<ELEMT_TYP, 2 * length_n> r2 = a2 * b2;

		LargeIntegerMeta<ELEMT_TYP, length_m> a2_l(a2), b2_l(b2);
		LargeIntegerMeta<ELEMT_TYP, 2 * length_m + 1> r_l_1(a1 * b2_l), r_l_2(a2_l * b1);

		LargeIntegerMeta<ELEMT_TYP, 2 * N> retVal(r2);								// copy lower bits
		retVal.merge_right_align( r1, -2 * length_n );								// copy higher bits

		//Less optimal...
		LargeIntegerMeta<ELEMT_TYP, 2 * N> sum_l( r_l_1 + r_l_2, -length_n );		// sum of middle bits
		retVal = retVal + sum_l;													// final add.

		return retVal;
	}

	LargeIntegerMeta  operator+(const LargeIntegerMeta& rhs) const
	{
		LargeIntegerMeta retVal(*this);

		std::bitset<ELEMT_SIZE+1> ovfw_flag, flbt_flag;
		const ELEMT_TYP high_bit_mask = (ELEMT_TYP(0x1))<<(ELEMT_BITS-1);
		const ELEMT_TYP full_bit_val  = ((ELEMT_TYP(0x1))<<ELEMT_BITS)-1;

		// first addition pass
		for (int i=0;i<ELEMT_SIZE;i++)
		{
			retVal.m_data[i] += rhs.m_data[i];
		}

		// collect necessary flags
		for (int i=0;i<ELEMT_SIZE;i++)
		{
			int high_bit_is_one = 0;

			high_bit_is_one += (m_data[i]&high_bit_mask)?1:0;
			high_bit_is_one += (rhs.m_data[i]&high_bit_mask)?1:0;
			high_bit_is_one += (retVal.m_data[i]&high_bit_mask)?0:1;

			ovfw_flag[i] = high_bit_is_one>=2? true:false;
			flbt_flag[i] = full_bit_val==retVal.m_data[i]? true:false;
		}

		ovfw_flag = ovfw_flag<<1;
		flbt_flag &= ovfw_flag;
		ovfw_flag |= flbt_flag<<1;

		// second pass add the overflow
		for (int i=0;i<ELEMT_SIZE;i++)
		{
			if (ovfw_flag[i])
			{
				retVal.m_data[i]++;
			}
		}
		
		return retVal;
	}

	LargeIntegerMeta  operator-(const LargeIntegerMeta& rhs) const
	{
		LargeIntegerMeta retVal;

		std::bitset<ELEMT_SIZE+1> borw_flag, zero_flag;

		// first addition pass
		for (int i=0;i<ELEMT_SIZE;i++)
		{
			bool need_to_borrow = m_data[i]<rhs.m_data[i];

			retVal.m_data[i] = m_data[i] - rhs.m_data[i];

			borw_flag[i] = need_to_borrow;
			zero_flag[i] = !(retVal.m_data[i]);
		}

		borw_flag = borw_flag<<1;
		zero_flag &= borw_flag;
		borw_flag |= zero_flag<<1;

		// second pass add the overflow
		for (int i=0;i<ELEMT_SIZE;i++)
		{
			if (borw_flag[i])
			{
				retVal.m_data[i]--;
			}
		}

		return retVal;
	}

	bool operator<(const LargeIntegerMeta& rhs) const
	{
		bool ret = false;

		for ( int i = ELEMT_SIZE-1; i>=0; --i )
		{
			if (m_data[i]<rhs.m_data[i])
			{
				ret = true;
				break;
			}
		}

		return ret;
	}

	template<int shift_bit_size>
	LargeIntegerMeta left_shift_bits() const
	{
		const int addit_elem = (shift_bit_size/ELEMT_BITS)+(shift_bit_size%ELEMT_BITS?1:0);
		const int left_bits	 = shift_bit_size%ELEMT_BITS;
		const int right_bits = ELEMT_BITS - left_bits;

		LargeIntegerMeta tempVal(*this,-shift_bit_size/ELEMT_BITS);
		LargeIntegerMeta retVal;

		// first pass left shift
		for (int i=0;i<ELEMT_SIZE;i++)
		{
			retVal.m_data[i] = tempVal.m_data[i]<<left_bits;
		}
		// second pass right shift
		for (int i=1;i<ELEMT_SIZE;i++)
		{
			retVal.m_data[i] |= tempVal.m_data[i-1]>>right_bits;
		}

		return retVal;
	}

	//ELEMT_TYP& operator[](const int i)
	//{
	//	return m_data[i];
	//}

	//************************************
	// Debug functions
	//************************************
	void debug_output_bitset(std::bitset<TOTAL_BITS>& pOut) const
	{
		for (int i=0;i<TOTAL_BITS;i++)
		{
			const int elm_idx = i/ELEMT_BITS;
			pOut[i] = ((m_data[elm_idx]>>(i%ELEMT_BITS))&0x1)? true:false;
		}
	}

	ELEMT_TYP m_data[N];

private:
	void clearMem(){
		memset(m_data,0,sizeof(m_data));
	}

	template<int M>
	void assign_right_align(const LargeIntegerMeta<ELEMT_TYP,M>& pLargNum, const int pElmRightOffset=0)
	{
		copy_right_align<M,true>(pLargNum,pElmRightOffset);
	}

	template<int M>
	void merge_right_align(const LargeIntegerMeta<ELEMT_TYP,M>& pLargNum, const int pElmRightOffset=0)
	{
		copy_right_align<M,false>(pLargNum,pElmRightOffset);
	}

	//************************************
	// Copy from a LargeIntegerMeta object with the same 
	// element type possibly in a different dimension. 
	// The offset is a signed integer showing how many elements
	// should be aligned rightward away to the right end of
	// this object.
	//************************************
	template<int M, bool if_clear>
	void copy_right_align(const LargeIntegerMeta<ELEMT_TYP,M>& pLargNum, const int pElmRightOffset)
	{
		const int &ths_size = ELEMT_SIZE;
		const int &pLN_size = M;

		if (if_clear)
		{
			this->clearMem();
		}

		//TODO: Throw a warning if rhs_size is bigger than lhs_size

		const int lft_pLN = pElmRightOffset - pLN_size;
		const int copy_end = std::min(std::max(-ths_size,lft_pLN),0);
		const int copy_start = std::min(std::max(-ths_size,pElmRightOffset),0);
		const int copy_size = copy_start - copy_end;
		const int ths_offset = -copy_start;
		const int pLN_offset = pElmRightOffset - copy_start;

		if(copy_size>0)
			memcpy( m_data+ths_offset, pLargNum.m_data+pLN_offset, copy_size * sizeof(ELEMT_TYP) );
	}
};

template<typename T, int N>
std::ostream& operator<<(std::ostream &pStream, const LargeIntegerMeta<T,N>& pData) {
	for ( int i=N-1;i>=0;i-- )
	{
		pStream.width(8);
		pStream<<std::hex<<std::right<<pData.m_data[i];
	}
	return pStream;
}

#include "LargeIntegerSpecialization.inl"